package org.example;

class Solution {

    public int minCut(String s) {
        boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
            dp[i][i + 1] = true;
        }
        for (int len = 2; len <= s.length(); len++) {
            for (int start = 0; start + len - 1 < s.length(); start++) {
                int end = start + len;
                if (s.charAt(start) == s.charAt(end - 1) && dp[start + 1][end - 1]) {
                    dp[start][end] = true;
                }
            }
        }
        int[] cut = new int[s.length() + 1];
        for (int i = 2; i <= s.length(); i++) {
            if (dp[0][i]) {
                cut[i] = 0;
                continue;
            }
            cut[i] = Integer.MAX_VALUE;
            for (int pos = 1; pos < i; pos++) {
                if (dp[pos][i]) {
                    cut[i] = Math.min(cut[i], 1 + cut[pos]);
                }
            }
        }
        return cut[s.length()];
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}